712D - Memory and Scores - CodeForces Solution

/* Code by pp_orange */
#include<bits/stdc++.h>
#define m_p(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define ll long long
#define ull unsigned long long
#define inf 0x7FFFFFFF
#define inff 9223372036854775807
#define rep(i,l,r) for(int i=l;i<r;++i)
#define repp(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r-1;i>=l;--i)
#define go(i,x,y) for(int i=fir[x],y=e[i];i;y=e[i=nxt[i]])
#define pii pair<int,int>
#define fi first
#define se second
#define p_q priority_queue
#define Kill(x) {cout<<x<<endl;return 0;}
#define all(x) x.begin(),x.end()
#define mod 1000000007
using namespace std;
inline int rd(){
    int x(0),f(1);char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
inline void out(int X){
	if(X<0) {X=~(X-1); putchar('-');}
	if(X>9) out(X/10);
	putchar(X%10+'0');
}
ll pw(int x,int d){
	if(!d)return 1;
	ll t = pw(x,d>>1);
	t = t*t%mod;
	if(d&1)return t*x%mod;
	return t;
}
//#define pp_orange
#define Base 202105
ll dp[2][Base<<1];
signed main(){
	#ifdef pp_orange
    freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	int a = rd();
	a -= rd();
	int k = rd();
	int t = rd();
	dp[0][Base+a] = 1;
	int nw = 1,lst = 0;
	t <<= 1;
	
	
	rep(i,0,t){
		memset(dp[nw],0,sizeof(dp[nw]));
		rep(j,1,(Base<<1))dp[lst][j] += dp[lst][j-1];
		rep(j,1,(Base<<1)){
			dp[nw][j] = (dp[lst][min(j+k,(Base<<1)-1)]-dp[lst][max(0,j-k-1)])%mod;
		}
		nw ^= 1;
		lst ^= 1;
	}
	
	ll ans = 0;
	rep(i,Base+1,(Base<<1)){
		ans = (dp[lst][i]+ans)%mod;
	}
	cout<<ans<<endl;
	return 0;
}